package myself.a005Heap;


import system2021.src.class06heap.Code02_Heap;

import java.util.PriorityQueue;

/**
 * @author 叶之越
 * Description 大头堆实现
 * Date 2021/1/23
 * Time 20:52
 * Mail 739153436@qq.com
 */
public class MaxHeap {
    private final int limit;
    private int[] heap;
    private int heapSize;

    public MaxHeap(int limit) {
        heap = new int[limit];
        this.limit = limit;
        heapSize = 0;
    }

    public static void main(String[] args) {
        // 小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>(new Code02_Heap.MyComparator());
        heap.add(5);
        heap.add(5);
        heap.add(5);
        heap.add(3);
        //  5 , 3
        System.out.println(heap.peek());
        heap.add(7);
        heap.add(0);
        heap.add(7);
        heap.add(0);
        heap.add(7);
        heap.add(0);
        System.out.println(heap.peek());
        while (!heap.isEmpty()) {
            System.out.println(heap.poll());
        }


        int value = 1000;
        int limit = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            int curLimit = (int) (Math.random() * limit) + 1;
            MaxHeap my = new MaxHeap(curLimit);
            int curOpTimes = (int) (Math.random() * limit);
            for (int j = 0; j < curOpTimes; j++) {

                if (my.isEmpty()) {
                    int curValue = (int) (Math.random() * value);
                    my.push(curValue);
                } else if (my.isFull()) {
                } else {
                    if (Math.random() < 0.5) {
                        int curValue = (int) (Math.random() * value);
                        my.push(curValue);
                    } else {
                    }
                }
            }
        }
        System.out.println("finish!");

    }

    public boolean isEmpty() {
        return heapSize == 0;
    }

    public boolean isFull() {
        return heapSize == heap.length;
    }

    public void push(int value) {
        if (heapSize == limit) {
            throw new RuntimeException("heap is full");
        }
        heap[heapSize] = value;
        heapInsert(heap, heapSize++);
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("heap is full");
        }
        swap(heap, 0, --heapSize);
        heapify(heap, 0, heapSize);
        return heap[heapSize];
    }

    // 从底部往上插入
    public void heapInsert(int[] arr, int index) {
        // 在没有插到最低端的时候不要停止，但是我发现，如果index=0的时候下标的计算为 -1/2=0 ，仍然是不越界的，可以跳出循环
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, (index - 1) / 2, index);
            index = (index - 1) / 2;
        }

        // 我之前的写法，比较臃肿
        /*while (index > 0) {
            int father = (index - 1) / 2;
            if (arr[father] < arr[index]) {
                swap(arr, father, index);
                index =  (index - 1) / 2;
            }else {
                break;
            }
        }*/
    }

    public void heapify(int[] arr, int index, int heapSize) {
        int leftChild = index * 2 + 1;
        while (leftChild + 1 <= heapSize) {

            // 这个逻辑比较绕，和while循环里面条件有上下文关系
            int maxChild = leftChild + 2 <= heapSize && arr[leftChild + 1] >= arr[leftChild]
                    ? leftChild + 1 : leftChild;
            if (arr[index] < arr[maxChild]) {
                swap(arr, index, maxChild);
                index = maxChild;
                leftChild = index * 2 + 1;
            } else {
                break;
            }
        }
    }

    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
